1. Field of the Invention
The present invention relates to an image deformation technique.
2. Description of the Related Art
A conventional image processing apparatus which performs image deformation stores input pixels corresponding to one frame in a memory first, and then calculates the coordinate values of the input pixels from the coordinate values of output pixels in the scan order of the output pixels by inverse transformation of coordinate transformation. This apparatus further repeats the operation of reading out pixels adjacent to the input pixels from the memory by using the integer parts of the coordinate values of the input pixels obtained by the inverse transformation and deciding the values of output pixels by interpolation calculation using the adjacent pixels and the fraction parts of the coordinate values of input pixels. These operations have implemented image processing configured to perform image deformation. The above method will be referred to as “read time coordinate transformation” hereinafter. For example, patent literature 1 (Japanese Patent Laid-Open No. 2005-135096) discloses an image processing method which segments an output image into tiles and performs read time coordinate transformation for each segmented tile.
When performing keystone correction for a front projector or lens correction for a camera, the enlargement rate from an input image to an output image ranges from the minimum of about 0.6 to the maximum of about 1.25. In addition, there is a restriction that video input/output operation must be implemented in real time. When implementing the above image processing method under the restriction that video input/output operation should be performed at 1 [pixel/cyc], the peak value of a necessary memory band becomes a total of (1+1/minimum value of enlargement rate) [pixels/cyc] for both write and read operations. If, for example, the minimum value of enlargement rate is 0.6, a memory band of 2.67 [pixels/cyc] is required at a peak time.
In contrast to this, the following is a scheme called “write time coordinate transformation”. This scheme calculates output coordinates by performing coordinate transformation of input pixels input in the scan order. The scheme then calculates storage destination addresses of the memory from the integer parts of the output coordinates. In addition, the scheme obtains coordinates in the input image from the integer parts of the output coordinates by inverse transformation of coordinate transformation. If the integer parts of the coordinates obtained by inverse transformation coincide with the coordinates of the original input pixels, the scheme obtains pixel values to be output by interpolation calculation using the input pixels, the adjacent pixels, and the fraction parts of the coordinate values obtained by inverse transformation of coordinate transformation. These pixel values are stored at the storage destination addresses obtained in advance.
The peak value of a necessary memory band in the write time coordinate transformation scheme becomes a total of (1+maximum value of enlargement rate) [pixels/cyc] for both write and read operations. When the maximum value of enlargement rate is 1.25, the peak value becomes 2.25 [pixels/cyc]. That is, the peak value of a memory band can be made smaller than that in read time coordinate transformation within the assumed range of enlargement rates.
However, with the above write time coordinate transformation without any change, some pixels may not be output. It is therefore necessary to take some countermeasures. For example, according to patent literature 2 (Japanese Patent Laid-Open No. 6-149993) which performs write time coordinate transformation, the generation of pixels which are not output is prevented by scanning the coordinates of input pixels for each sub-pixel.
In the scheme disclosed in patent literature 1, the peak value of a necessary memory band becomes large within the assumed range of enlargement rates. In the scheme disclosed in patent literature 2, even when scanning sub-pixels on a ½ pixel basis in both the X-axis direction and the Y-axis direction, it is necessary to perform computation corresponding to four points in coordinate transformation and computation corresponding to four points in inverse transformation. In projection transformation, the computation amount for coordinate transformation is equal to that for inverse transformation, and both the computations include division. For this reason, the hardware implementation of the scheme disclosed in patent literature 2 will result in a large circuit amount. The software implementation of the scheme will result in a deterioration in processing performance.